import java.util.ArrayDeque;
import java.util.Deque;

public class Trap {
    public int trap(int[] height) {
        Deque<Integer> deque = new ArrayDeque<>();
        int ret = 0;
        for (int i = 0; i < height.length; i++) {
            if (deque.isEmpty() || height[i] <= height[deque.peekLast()]) {
                deque.addLast(i);
            } else {
                while (!deque.isEmpty() && height[i] > height[deque.peekLast()]) {
                    int mid = deque.pollLast();
                    if (deque.isEmpty()) {
                        break;
                    }
                    int left = deque.peekLast();
                    ret +=  (Math.min(height[i], height[left])-height[mid]) * (i-left-1);
                }
                deque.addLast(i);
            }
        }
        return ret;
    }

    public static void main(String[] args) {
//        System.out.println(new Trap().trap(new int[]{0,1,0,2,1,0,1,3,2,1,2,1}));
        System.out.println(new Trap().trap(new int[]{4,2,0,3,2,5}));
    }
}
